There are many variations on partition functions for graph homomorphisms orcolorings. The case considered here is a counting or hard constraint problem inwhich the range or color graph carries a free and vertex transitive Abeliangroup action so that the colors are identified with the elements of this group.A Fourier transform is used to obtain an expansion for the numbers of coloringswith terms indexed by isthmus free subgraphs of the domain. The terms areproducts of a polynomial in the edge density a of the color graph and thenumber of colorings of the indexing subgraph of the domain into thecomplementary color graph. The polynomial in a is independent of the colorgroup and the term has order (1-a) to the r where r is the number of verticesminus the number of components in the indexing subgraph. Thus if (1-a) is smallthere is a main term indexed by the empty subgraph which is a polynomial in aand the first dependence on the coloring group occurs in the lowest ordercorrections which are indexed by the shortest cycles in the graph and are oforder (1-a) to the g-1 where g is the length of these shortest cycles. The maintheorem is stated as a reciprocity law. Examples are given in which thecoloring groups are long cycles and products of short cycles and adjacentvertices are required to have distant rather than distinct colors. Thechromatic polynomial of a graph corresponds to using any group and taking theallowed set to be the complement of the identity.
展开▼
